The invention relates to a block motion estimation method for estimating a motion vector on the basis of a position of a block in a current picture compared to a position of the found block in a reference picture.
In the field of encoding a video sequence (video encoding), the compression of video data has become a very important issue for reducing the amount of data needed to be transmitted and/or stored for the encoding of a plurality of pictures in a quality which is sufficiently high for a user.
A very important factor with respect to video data compression is the motion estimation between subsequent pictures of the video sequence, which is used to extract motion information from the video sequence. The extracted motion information is used for avoiding or at least reducing the temproral redundancy in subsequent video pictures.
Block-matching motion estimation is widely applied in many motion-compensated video coding techniques/standards such as ISO MPEG-1/2/4 and ITU-T H.261/262/263/263+/263L, which is aimed to exploit the strong temporal redundancy between successive frames. By partitioning a current frame into non-overlapping rectangular blocks/macroblocks of equal size, a block matching method attempts to find a block from a reference frame (past or future frame) that best matches a predefined block in the current frame. Matching is performed by minimizing a matching criterion, which in most cases is the mean absolute error between this pair of blocks. The block in the reference frame moves inside a search window centred around the position of the block in the current frame. The best matched block producing the minimum distortion is searched within the search window in the reference frame. The displacement of the current block with respect to the best matched reference block in x and y directions composes the motion vector assigned to this current block.
However, the motion estimation is quite computational intensive and can consume up to 80% of the computational power of the encoder if the full search is used by exhaustively evaluating all possible candidate blocks within a predefined search window. Therefore, fast algorithms are highly desired to significantly speed up the procedure without sacrificing the distortion sharply.
Many computationally efficient variants were developed, typically among which are the so-called three-step search, the new three-step search, the four-step search, the block-based gradient descent search and the diamond search algorithms, compare for instance references [1], [2], [3], [4], [5].
In the block-based motion estimation, the search pattern with different shapes or sizes has a great impact on the reachable search speed and the resulting distortion performance.
On one hand, in the three-step search, the new three-step search, the four-step search and the block-based gradient descent search algorithms, square-shaped search patterns of different sizes are employed. These topics are described in [4] and [5].
On the other hand, the diamond search algorithm, as described in [2] and [3], adopts a diamond-shaped search pattern, which has demonstrated faster processing time with marginally worse distortion in comparison with the three-step search, the new three-step search and the four-step search.
The search pattern used in the diamond search algorithm has a rectangular, diamond shape. Two different sizes of diamonds are employed. The larger one consists of nine search points (also denoted as checking points), of which eight search points surround a central search point. The small diamond search pattern consists of five inner search points, of which four inner search points surround a central search point to compose the diamond shape.
Recently, the inventors of the present invention have proposed a hexagon-based search algorithm (PCT/SG00/00176, unpublished). The basic idea of this concept can generally be seen in a hexagon-based search algorithm in the block motion estimation in a sequence of pictures, i.e. a video sequence, where the search algorithm can achieve significant speed improvement over the diamond search algorithm with similar distortion performance. The hexagon-based search algorithm employs two different sizes of hexagonal search patterns. The larger one consists of seven search points, of which six search points surround a central search point. The small hexagon search pattern comprises five inner search points, of which four inner search points surround a central search point.
However, there is still the emerging need to improve the processing speed for motion estimation.